⟸ Go Back ⟸
Exercise 4 (Homework 7).
(polynomial-time reductions)

Polynomial-time reductions

Consider the relation \le_m^p among languages and justify your answers to the following questions.

  1. Is \le_m^p reflexive? That is, does it hold that A \le_m^p A for any language A?
  2. Is \le_m^p symmetric? That is, does it hold that if A \le_m^p B, then B \le_m^p A for any languages A, B?
  3. Is \le_m^p antisymmetric? That is, does it hold that A \le_m^p B and B \le_m^p A imply A = B for any languages A, B?
  4. Is \le_m^p transitive? That is, does it hold that A \le_m^p B and B \le_m^p C imply A \le_m^p C for any languages A, B, and C?
Polynomial many-one reductions (or Karp reductions)

Recall that given two languages A, B over the same alphabet \Sigma, we say that A polynomial-time reduces to B (denoted as A\leq_m^p B or A\leq_p B) if there exists a total function f:\Sigma^*\to\Sigma^* computable in polynomial time s.t. for every w\in \Sigma^*, w\in A if and only if f(w)\in B.

A useful property is the closure of the classes \mathsf{P}, \mathsf{NP} i \mathsf{coNP} under polynomial-time reductions, that is, given A\leq_m B,

  • if B\in \mathsf{P}, then A\in \mathsf{P},
  • if B\in \mathsf{NP}, then A\in \mathbf{NP}, and
  • if B\in \mathsf{coNP}, then A\in \mathbf{coNP}.

The m in \leq_m stands for the fact that f is many-one, that is, not necessarily injective.